package Test_1114;

import Test_1106.MySingleList;

import java.util.Stack;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
//判断回文
class PalindromeList {
    public boolean chkPalindrome(MySingleList.ListNode A) {
        MySingleList mySingleList=new MySingleList();
        MySingleList.ListNode slow= mySingleList.head;
        MySingleList.ListNode fast= mySingleList.head;
        while(fast!=null && fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        MySingleList.ListNode cur=slow.next;
        while(cur!=null){
            MySingleList.ListNode curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        while (mySingleList.head!=slow){
            if(mySingleList.head.val!=slow.val){
                return false;
            }
            if(mySingleList.head==slow){
                return true;
            }
            mySingleList.head=mySingleList.head.next;
            slow=slow.next;
        }
        return true;
    }
}
class MinStack {
    public Stack<Integer> stack;
    public Stack<Integer> minStack;
    public MinStack() {
          stack=new Stack<>();
          minStack=new Stack<>();
    }
//放入元素到stack
// 放入元素到minstack
    //如果为空，先放元素；
    //如果不为空，比较大小，小于等于了放进去
    public void push(int val) {
        stack.push(val);
       if(minStack.empty()){
           minStack.push(val);
       }else{
           int peekVal=minStack.peek();
           if(val<=peekVal){
               minStack.push(val);
           }
       }
    }
//拿出：
    //看minstack中是否有最小值，如果有拿出来
    public void pop() {
         if(stack.empty()){
             return ;
         }
         int popVal=stack.pop();
         if(popVal==minStack.peek()){
             minStack.pop();
         }
    }
    //stack栈顶元素
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
//minstack栈顶元素
    public int getMin() {
        if(stack.empty()){
            return -1;
        }
        return minStack.peek();
    }
}
public class Solution {
    public boolean IsPopOrder (int[] pushV, int[] popV) {
           Stack<Integer> stack =new Stack<>();
           int j=0;
        for (int i = 0; i < pushV.length; i++) {
           stack.push(pushV[i]);
           //满足条件出栈，出栈一次j++；
           while ( j<popV.length && !stack.empty()&&stack.peek()==popV[j] ){
               stack.pop();
               j++;
           }

        }
        return stack.empty();
    }
    //逆波兰表示法
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack=new Stack<>();
        for (String str:tokens){
            //如果不是操作符，放进去
            if(!isOperator(str)){
                //字符串转为整数
                int x=Integer.parseInt(str);
                stack.push(x);
            }else {
                //如果是操作符，将里面的数拿出来
                int val2=stack.pop();
                int val1=stack.pop();
                //操作符运算
                switch (str){
                    //把运算的数放到栈里面
                    case "+":
                        stack.push(val1+val2);
                        break;
                    case "-":
                        stack.push(val1-val2);
                        break;
                    case "*":
                        stack.push(val1*val2);
                        break;
                    case "/":
                        stack.push(val1/val2);
                        break;
                }
            }
        }
    return stack.pop();
    }
    private boolean isOperator(String ch){
        if(ch.equals("+")||ch.equals("-")||ch.equals("*")||ch.equals("/")){
            return true;
        }
        return false;
    }
}
